package niuke;

/**
 * description:
 * author:张腾
 * date:2021-06-27
 */

/**
 * 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
 * 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
 * 你不能更改节点中的值，只能更改节点本身。
 * 要求空间复杂度 O(1)
 */
public class NC50 {
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode pre =dummy;
        ListNode end = dummy;

        while (end.next!=null){
            for (int i = 0; i < k && end!=null; i++) end = end.next;
            if (end==null) break;
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            end = pre;
        }
        return dummy.next;
    }
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}
